package com.huawei.controller;

import jdk.nashorn.internal.ir.WhileNode;

import java.io.*;
import java.util.Deque;
import java.util.LinkedList;

/**
 * description
 *
 * @author cwx1134046
 * @since 2023-01-28
 */
public class ShortestSubarray {
    /**
     *给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
     *
     * 子数组 是数组中 连续 的一部分。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：nums = [1], k = 1
     * 输出：1
     * 示例 2：
     *
     * 输入：nums = [1,2], k = 4
     * 输出：-1
     * 示例 3：
     *
     * 输入：nums = [2,-1,2], k = 3
     * 输出：3
     *
     */
    static public int shortestSubarray(int[] nums, int k) {
        Deque<Element> deque = new LinkedList<>();
        deque.add(new Element(0,0));
        int res = nums.length +1;
        long preSum = 0;
        for(int i= 0; i<nums.length ; i++ ){
            preSum =  nums[i] + preSum;
            Element element = new Element(i + 1, preSum);

            while(!deque.isEmpty() && element.getPreSum() - deque.peekFirst().getPreSum() >= k){
                res = Math.min(res,element.getIndex() - deque.peekFirst().getIndex());
                deque.pollFirst();
            }

            while(!deque.isEmpty() && deque.peekLast().getPreSum() > element.getPreSum()) {
                deque.pollLast();
            }
            deque.addLast(element);
        }
        if(res <  nums.length +1) {
            return res;
        }else {
            return -1;
        }
    }

    static public class Element{
        private int index;
        private long preSum;

        public Element (int index ,long preSum) {
            this.index = index;
            this.preSum = preSum;
        }

        public int getIndex(){
            return this.index;
        }

        public long getPreSum() {
            return this.preSum;
        }
    }
}
